Remove element [Two pointers]¶
Time: O(N); Space: O(1); easy
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Example 1:
Input: nums = [3,2,2,3], val = 3
Output: length = 2, with the first two elements of nums being 2.
Note:
It doesn’t matter what you leave beyond the returned length.
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
Notes:
The order of those five elements can be arbitrary.
It doesn’t matter what values are set beyond the returned length.
Clarification¶
Confused why the returned value is an integer but your answer is an array? Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this: // nums is passed in by reference. (i.e., without making a copy) len = removeElement(nums, val) // any modification to nums in your function would be known by the caller. // using the length returned by your function, it prints the first len elements. for i in range(len): print(nums[i])
Hints:
The problem statement clearly asks us to modify the array in-place and it also says that the element beyond the new length of the array can be anything. Given an element, we need to remove all the occurrences of it from the array. We don’t technically need to remove that element per-say, right?
We can move all the occurrences of this element to the end of the array. Use two pointers!
Yet another direction of thought is to consider the elements to be removed as non-existent. In a single pass, if we keep copying the visible elements in-place, that should also solve this problem for us.
1. Two Pointers¶
Intuition Since this question is asking us to remove all elements of the given value in-place, we have to handle it with O(1)O(1) extra space. How to solve it? We can keep two pointers ii and jj, where ii is the slow-runner while jj is the fast-runner.
Algorithm When nums[j] equals to the given value, skip this element by incrementing j. As long as nums[j] <> val, we copy nums[j] to nums[i] and increment both indexes at the same time. Repeat the process until j reaches the end of the array and the new length is i.
This solution is very similar to the solution to Remove Duplicates from Sorted Array
[7]:
class Solution1(object):
"""
Time: O(n). Assume the array has a total of n elements, both i and j traverse at most 2n steps.
Space: O(1).
"""
def removeElement(self, nums, val):
"""
:type nums: List[int]
:rtype: int
"""
i = 0
for j in range(len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1
return i
[8]:
s = Solution1()
nums = [3,2,2,3]
val = 3
assert s.removeElement(nums, val) == 2
print(nums[:2])
nums = [0,1,2,2,3,0,4,2]
val = 2
assert s.removeElement(nums, val) == 5
print(nums[:5])
[2, 2]
[0, 1, 3, 0, 4]
2. Two Pointers - when elements to remove are rare¶
Intuition Now consider cases where the array contains few elements to remove. For example, nums = [1,2,3,5,4], val = 4. The previous algorithm will do unnecessary copy operation of the first four elements. Another example is nums = [4,1,2,3,5], val = 4. It seems unnecessary to move elements [1,2,3,5] one step left as the problem description mentions that the order of elements could be changed.
Algorithm When we encounter nums[i] = val, we can swap the current element out with the last element and dispose the last one. This essentially reduces the array’s size by 1.
Note:
The last element that was swapped in could be the value you want to remove itself.
But don’t worry, in the next iteration we will still check this element.
[9]:
class Solution2(object):
"""
Time: O(n). Both i and n traverse at most n steps.
In this approach, the number of assignment operations is equal to the number of elements to remove.
So it is more efficient if elements to remove are rare.
Space: O(1).
"""
def removeElement(self, nums, val):
"""
:type nums: List[int]
:rtype: int
"""
i, last = 0, len(nums) - 1
while i <= last:
if nums[i] == val:
nums[i], nums[last] = nums[last], nums[i]
last -= 1
else:
i += 1
return last + 1
[10]:
s = Solution2()
nums = [3,2,2,3]
val = 3
assert s.removeElement(nums, val) == 2
print(nums[:2])
nums = [0,1,2,2,3,0,4,2]
val = 2
assert s.removeElement(nums, val) == 5
print(nums[:5])
[2, 2]
[0, 1, 4, 0, 3]